import java.util.*;

class Student {

}



public class TestMap {

    //1.统计10个数据当中，不重复的数据[去重]
    public static void notRepeat(int[] array) {
        //利用HashSet不能存放相同的数据，直接add - TreeSet也可以
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            set.add(array[i]);
        }
        System.out.println(set);
    }

    //2.统计10个数据，第一次相同的数
    public static void firstRepeat(int[] array) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if (!set.contains(array[i])) {
                //不是相等的数 - 继续添加
                set.add(array[i]);
            } else {
                //是相等的数 - 输出后跳出
                System.out.println(array[i]);
                return;
            }
        }
    }

    //3.统计10个数据，每个数据出现的次数
    public static void occurrences(int[] array) {
        HashMap<Integer, Integer> map = new HashMap<>();//hashMap可以记录数据个数
        for (int i = 0; i < array.length; i++) {
            //数据如果是没有就添加
            int key = array[i];
            if (null == map.get(key)) {
                map.put(key, 1);
            } else {
                //有 - key是出现的次数
                int val = map.get(key);
                map.put(key, val + 1);//出现一次个数加一个
            }
        }

        //System.out.println("dcsdc");

        //key出现几次
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            System.out.println("key：" + entry.getKey() + "出现了：" + entry.getValue() + "次");
        }
    }

    /**
     * @ 哈希表OJ题
     *
     * **/
    //1.只出现一次的数
    public static int onceNumber(int[] array) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if (!set.contains(array[i])) {
                //set中没有就添加
                set.add(array[i]);
            } else {
                //有就删除
                set.remove(array[i]);
            }
        }
        for (int i = 0; i < array.length; i++) {
            if (set.contains(array[i])) {
                return array[i];
            }
        }
        return -1;
    }

    //2.赋值带随机指针的链表
    class Node {
        int val;//值域
        Node next;//地址域
        Node random;//random域

        //构造方法
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        //先遍历原链表，存储对应关系
        Node cur = head;
        while (cur != null) {
            Node node = new Node(cur.val);//新建结点
            map.put(cur, node);//cur是老结点，node是新节点地址
            cur = cur.next;//指向下一个
        }
        //cur重新指向原表头结点
        //在遍历一次将新表连接起来
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);//域链接结点的next
            map.get(cur).random = map.get(cur.random);//random域指向第三个节点
            cur = cur.next;//指向下一个
        }
        return map.get(head);//返回新表头结点
    }

    //3.宝石与石头
    public static int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> set = new HashSet<>();
        int count = 0;//计数器
        //遍历宝石数组将宝石放大set中
        for (int i = 0; i < jewels.length(); i++) {
            char ch = jewels.charAt(i);//获取字符
            set.add(ch);//放入ch中
        }

        //遍历石头数组将石头看石头是不是宝石
        for (int i = 0; i < stones.length(); i++) {
            char ch = stones.charAt(i);//获取字符
            //比较
            if (set.contains(ch)) {
                //此时拿到的字符是宝石 - 个数加一个
                count++;
            }
        }
        return count;
    }

    //4.旧键盘
    private static void keyBoard(String shouldChar, String actualChar) {
        //定义Set
        HashSet<Character> set = new HashSet<>();
        //toUpperCase()转成大写，toCharArray()转成数组
        for (char ch : actualChar.toUpperCase(Locale.ROOT).toCharArray() ) {
            set.add(ch);//放入Set中
        }
        HashSet<Character> bokenSet = new HashSet<>();
        for (char ch : actualChar.toUpperCase(Locale.ROOT).toCharArray() ) {
            //Set中有
            if (!set.contains(ch) && !bokenSet.contains(ch)) {
                bokenSet.add(ch);
                System.out.print(ch);
            }
        }
    }

    //前k个高频单词
    private static List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        //遍历words数组，统计当前每个字符串出现的次数
        for (String word : words) {
            if (map.get(word) == null) {
                //map中没有
                map.put(word, 1);
            } else {
                //map中有
                Integer val = map.get(word);
                map.put(word, val + 1);
            }
        }
        //单词的次数一统计完毕
        //建立大小为k的小根堆，每个元素就是一个Entry
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        //遍历Map中的每一个Entry
        for (Map.Entry<String, Integer> entry: map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String, Integer> top = minHeap.peek();
                //出堆
                if(entry.getValue().compareTo(top.getValue()) > 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else {
                    //频率相同
                    if (entry.getValue().compareTo(top.getValue()) == 0) {
                        if (top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        } else {

                        }
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }
        Collections.reverse(ret);
        return ret;
    }

    public static void main(String[] args) {
        String[] words = {"hello", "hello", "hello", "li", "li", "long", "world"};
        topKFrequent(words, 2);
    }

    public static void main9(String[] args) {
        Scanner input = new Scanner(System.in);
        //多组输入
        while (input.hasNextLine()) {
            String shouldChar = input.nextLine();//应该输出的字符
            String actualChar = input.nextLine();//实际输出的字符
            //调用方法
            keyBoard(shouldChar, actualChar);
        }
    }
    public static void main8(String[] args) {
        String[] jewels = {"a, A"};//宝石数组
        String[] stones = {"a, A, A, b, b, b"};//石头数组
        //           int ret = numJewelsInStones(jewels, stones);
        //System.out.println(ret);
    }

    public static void main7(String[] args) {
        int[] array = {1, 2, 3, 3, 1, 4, 4};
        int ret = onceNumber(array);
        System.out.println(ret);
        //occurrences(array);
    }

    public static void main6(String[] args) {
        int[] array = new int[10];
        int[] arrays = {1, 2, 4, 3, 1, 4, 3, 2};
        occurrences(arrays);
        Random random = new Random();//随机数
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(5);//随机数范围是0~5
        }
        //去重前
        System.out.println("去重前:" + Arrays.toString(array));
        System.out.println("整体的数据:" + Arrays.toString(array));
        notRepeat(array);
        firstRepeat(array);
    }

    public static void main5(String[] args) {
        HashSet<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(1);
        System.out.println("size:" + set);
        System.out.println("size:" + set.size());
    }
    public static void main4(String[] arges) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("hello", 1);
        map.put("world", 2);
        System.out.println(map);
        System.out.println(map.get("hello"));
    }

    public static void main3(String[] args) {
        HashMap<Student, Integer> map = new HashMap<>();
        map.put(new Student(), 2);
        map.put(new Student(), 1);
        map.put(null, null);
        System.out.println(map.get("hello"));
    }

    public static void main1(String[] args) {
        TreeSet<Student> set = new TreeSet<>();
        set.add(new Student());//无法比较
    }

    //字符串中的第一个唯一字符
    public int firstUniqChar(String s) {
        int[] array = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            array[ch - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (array[ch - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }

    public static void main2(String[] args) {
        TreeSet<String> set = new TreeSet<>();
        set.add("hello");
        set.add("world");
        //set.add("hello");//只能添加一个hello
        System.out.println(set);
        System.out.println(set.contains("hello"));
        System.out.println(set.contains("abcd"));
    }
}
